15.1 並行GCの正当性

正当な並行コレクタの2要件

安全性(safety)

コレクタは"少なくとも"すべての到達可能オブジェクトが失われないよう維持しなければならない

活性(liveness)

コレクタは最終的にGCサイクルを完了しなければならない

死んだオブジェクトを回収するではない

三色抽象化の復習

白

コレクタが未到達なオブジェクト。終了時に白いままならごみ。

灰

オブジェクト自体にはコレクタが到達しているが、フィールドの一部が未走査。オブジェクトが指しているオブジェクトに白いものが存在しているかも。

黒

オブジェクトにコレクタが到達し、かつ全フィールドが走査済み。

並行にGCすると、灰が白黒の境界ではなくなるかもしれないらしい。

三色があやうくなる例

code:15-1.py

atomic Write(src, i, new):

オブジェクトsrcのあるフィールドを、oldからnewに変更するWrite操作。

このWriteがGCと並行して行われることを考える。

srcが白もしくは灰色なら、書き換えても問題ない

コレクタがsrcのフィールドをあとで走査するから

srcが黒色のとき :: oldは黒もしくは灰色

newが黒もしくは灰色なら問題ない

newが白いと、やばい

具体的には、newがsrcから指されているにもかかわらず解放されてしまう可能性がある

これをオブジェクトが"迷子"になるという

そもそもインクリメンタルGC一般に起こる問題では?

読む限りはインクリメンタルGCにも起こる問題だと思う．あとで「インクリメンタルGCや並行GCの安全性を見た」みたいな文面があるのでタイトルのせいでややこしくなってそう（suibaka

オブジェクトが迷子になる条件(この場合に"限る"!!らしい)

迷子になるオブジェクトをXとすると、まずXは白い。加えて、

1. ミューテータがXへのポインタを黒いオブジェクトに書き込み、かつ

2. 灰色オブジェクトからXへの"経路"がすべて破壊される

灰色オブジェクトからポインタを複数回たどってXに辿りつくような経路が存在しなくなる

オブジェクトが迷子にならないための不変条件

弱い三色不変条件

黒いオブジェクトが指しているすべての白いオブジェクトが"灰色保護"されている

"灰色保護"は、ある灰色オブジェクトからの経路が存在する状態

強い三色不変条件(弱い不変条件より強い)

黒いオブジェクトは白いオブジェクトを指さない

並行かつコピーしないGCは、弱い三色不変条件を守れば十分

並行コピーGCだと、強い三色不変条件を守らないといけない

コピーGCでは、from空間からto空間にオブジェクトを移し、from空間のオブジェクト全てごみになる。

from空間のオブジェクトは全て"白くないと"いけない

(並行でないGCでは強い不変条件が勝手に守られる)

精度

以下の3つにはトレードオフがある

精度(ごみをどれだけ回収できたか) (= 回収できたゴミ / 全部のゴミ)

効率(スループット) (= GCがオブジェクトを触った回数 / 生成されたオブジェクトの個数)

不可分性(どれだけ並行性を高められるか)

ストップザワールドGC

精度は最大(ごみを全て回収)

不可分性はなし(並行性なし)

不可分性を高めたGC

精度の悪化

不可分操作のためのオーバーヘッド

並行コレクタの完全性(全てのごみはいつか回収される)が保証されていることが望ましい

ミューテータの色

ミューテータスレッドの色を、ミューテータのルートの色として定義する

ミューテータは、ミューテータのルートから辿れるものにしかアクセスできないという仮定。たとえばスレッドスタックとか。

(たぶん白いミューテータはない。なぜならミューテータのルートがごみとして回収されることはないため)

灰色のミューテータ

コレクタがルートを未走査、もしくはルートの再走査が必要

ルートが白、灰色、黒のオブジェクトを参照しうる

黒いミューテータ

コレクタがルートを走査済み

強い三色不変条件のもとで、ルートが黒もしくは灰色オブジェクトのみを参照

弱い三色不変条件のもとで、ルートが参照している白いオブジェクトは全て灰色保護されている

灰色ミューテータを許す並列GCアルゴリズムにおいては、

GCの1サイクルを終わらせるために、ミューテータスレッドを停止させる必要があるかも。

灰色ミューテータの未走査な参照を追っているうちに、そのミューテータルートに新たな灰色オブジェクトが追加されて...を無限に繰り返すかもなので

オンザフライコレクタでは、ミューテータを黒(走査済み)と灰(未走査)に分類し、さらに各ミューテータスレッドのルート集合を黒と灰に分割したりする。

スレッドのスタックのトップフレームだけを走査して黒くし、残りは灰色のままにしたりするらしい。

割り付けの色

割りつけられたオブジェクトの色はミューテータの色と整合性(不変条件を満たす)がとられている必要がある。

黒で割りつけると、とりあえず安全。

しかし、黒や灰色で割りつけてしまうと、今回のGCサイクルでは回収されない(すぐ捨ててしまっても)

灰色のミューテータは、白いオブジェクトを割り付けることが可能

黒いミューテータは、白いオブジェクトを割り付けられない(弱い不変条件さえ破ってしまう)

（弱い不変条件のもとで）白いオブジェクトへの参照が生きているオブジェクトに格納されるのは(灰色の)境界の前方(すなわち白色オブジェクトたちのいるところ)に限られるならOK

後方 | (黒色) -> (灰色) -> (新しい白色) | 前方 (GCが時間的にあとでたどり着く)

以降の2節はどうやってオブジェクトを迷子にしないかの解決法

インクリメンタルアップデートによる解法

『1. ミューテータがX(白色)へのポインタを黒いオブジェクトに書き込み』を防ぐことで解決

黒いオブジェクトが白いオブジェクトを参照したときは、その白いオブジェクトを保守的に生きているとみなす。

具体的には、ライトバリアを用いてどちらかのオブジェクトの色を変更する。

黒いミューテータがヒープから白い参照をロードするときも、ライトバリアを用いて色を変更する。

(たぶん強い不変条件が保たれる)

スナップショットによる解法

『2. 灰色オブジェクトからX(白色)への"経路"がすべて破壊される』を防ぐことで解決

GC の開始時点で生きていたオブジェクトの集合を保存することで解決

弱い不変条件が保たれる

ミューテータが白いポインタを灰色もしくは白いオブジェクトから削除すると(ライトバリアを用いて)コレクタに通知され、生きていたオブジェクト集合に加えられる。ルート集合に関しては、GCサイクルの最初でミューテータのルートを走査して、ミューテータを黒にする(このときミューテータのスナップショットが保存されたととらえることもできる)。このため、スナップショットGCのミューテータはすべて黒い。

ルート集合はポインタの値であってポインタへのアドレスではない

つまり

code: hoge.c

Obj *p = new Obj;

// のときルート集合は {p} であって {&p} ではない